package ac_automaton

import "container/list"

/* AC 自动机
解决的问题：
	如文章： “abcdefghijk” 字符串列表：【["abc", "aefg", "cde", "fgh"]
	要求返回文章所包含的字符串列表中的字符串组成的列表。
*/

func NewACAutomaton() *ACAutomaton {
	ac := &ACAutomaton{}
	ac.Root = NewACNode()
	return ac
}

func NewACNode() *ACNode {
	return &ACNode{
		Next: make([]*ACNode, 26),
	}
}

type ACNode struct {
	End    string // 当End为空时，EndUse字段无效
	EndUSe bool   // 作为结尾是否已经使用过用于搜集答案了
	Next   []*ACNode
	Fail   *ACNode
}

type ACAutomaton struct {
	Root *ACNode
}

func (ac *ACAutomaton) Insert(s string) {
	cur := ac.Root
	path := 0
	for i := 0; i < len(s); i++ {
		path = int(s[i] - 'a')
		if cur.Next[path] == nil {
			cur.Next[path] = NewACNode()
		}
		cur = cur.Next[path]
	}
	cur.End = s
}

func (ac *ACAutomaton) Build() {
	// 采用队列的方式进行宽度优先遍历
	queue := list.New()
	queue.PushBack(ac.Root)
	var cur   *ACNode
	var cfail *ACNode
	for queue.Len() != 0 {
		cur = queue.Remove(queue.Front()).(*ACNode)
		for i := 0; i < 26; i++ { // 遍历所有的路
			if cur.Next[i] != nil { // 找到所有有效的路
				cur.Next[i].Fail = ac.Root
				cfail = cur.Fail
				for cfail != nil {
					if cfail.Next[i] != nil {
						cur.Next[i].Fail = cfail.Next[i]
						break
					}
					cfail = cfail.Fail
				}
				queue.PushBack(cur.Next[i])
			}
		}
	}
}

func (ac *ACAutomaton) ContainWords(content string) []string {
	var ans []string
	var follow *ACNode
	cur := ac.Root
	path := 0
	for i:=0; i<len(content); i++ {
		path = int(content[i]- 'a') // 路
		// 如果当前的字符串来到当前的路没匹配出来，就随着fail方向走向下条路径去
		// 如果当前cur节点，没有Path的路，就通过fail，跳到别的前缀上去
		for cur.Next[path] == nil && cur != ac.Root {
			cur = cur.Fail
		}
		// 1) 现在来到的路径，是可以继续匹配的
		// 2) 现在来的节点已经是头了
		if cur.Next[path] != nil {
			cur = cur.Next[path]
			follow = cur
		} else {
			follow = ac.Root
		}
		for follow != ac.Root {
			if follow.EndUSe == true {
				break
			}
			// 不同的需求在这一段之间修改
			if follow.End != "" {
				ans = append(ans, follow.End)
				follow.EndUSe = true
			}
			follow = follow.Fail
		}
	}
	return ans
}
